package day20210627;

import treenode.SimpleTreeNode;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 左子树的所有节点都小于当前节点，右子树的所有节点都大于当前节点，并且每棵子树都具有上述特点
 * @author lizy4
 * @date 2021/6/27 15:44
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.right.left = new SimpleTreeNode(7);
        simpleTreeNode.left = new SimpleTreeNode(2);
        System.out.println(solution.lowestCommonAncestor(simpleTreeNode,simpleTreeNode.right.right,simpleTreeNode.right.left));
    }

    private SimpleTreeNode lowestCommonAncestor(SimpleTreeNode root, SimpleTreeNode p, SimpleTreeNode q) {
        if(root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        if(root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }
}
